When a computer application provides data to a device for printing and/or display, an intermediate description of the page is often given to device driver software in a page description language (PDL), which provides descriptions of graphic objects to be rendered onto the page or display. This contrasts with some arrangements where raster image data is generated directly by the application and transmitted for printing or display. Examples of page description languages include Canon's LIPS™ and HP's PCL™.
Equivalently, the application may provide a set of descriptions of graphic objects in function calls to a graphics device interface layer, such as the Microsoft™ Windows GDI. The printer driver for the associated target printer is the software that receives the graphic object descriptions from the GDI layer. For each object, the printer driver is responsible for generating a description of the object in the page description language that is understood by the rendering system of the target printer.
The printer's rendering system contains a PDL interpreter that parses the graphic object descriptions and builds a display list of graphics object data. The rendering system also contains a raster image processor (RIP) that processes the display list and renders the data to pixel values comprising e.g. C, M, Y and K channels. Once in this format, the printer prints the page.
Most RIPs utilize a large volume of memory, known to the art as a framestore or a page buffer, to hold a pixel-based image data representation of the page or screen for subsequent printing and/or display. Typically, the outlines of the graphic objects are calculated, filled with color values and written to the framestore. For two-dimensional graphics, objects that appear in front of other objects are simply written into the framestore after the background objects, thereby replacing the background objects on a pixel by pixel basis. This is commonly known to the art as “Painter's algorithm”. Objects are considered in priority order from the rearmost object to the foremost object. Typically each object is rasterised in scanline order and pixels are written to the framestore in sequential runs along each scanline. Some RIPs allow objects to be composited with other objects. For example a logical or arithmetic operation can be specified and performed between one or more graphics objects and the pixels already rendered in the framestore. In these cases, the rendering principle remains the same: objects (or groups of objects) are rasterised in scanline order, and the result of the specified operation is calculated and written to the framestore in sequential runs along each scanline.
There are a number of problems with the Painter's algorithm rendering method. One of the problems is that many pixels which are written to the framestore by rendering an object are over-written when rendering later objects. There is a clear disadvantage in using resources to write pixel data into a framestore that will at a later stage be over-written.
Another problem is that when an object requires compositing, pixels beneath the object are typically read from the framestore and combined in some way with the pixels of the object. If the pixels in the framestore are stored in a lower bit-depth than the object requiring compositing, then most compositing operations generate an incorrect result. This is the case when the graphics object is, for example, an 8 bit per channel RGBA bitmap and the framestore holds one bit per channel half-toned pixel data. This can occur because pixel values are often stored in a framestore at the bit depth required for printing. Although it is possible to store pixels at the full 8 bits per channel, an 8 bit per channel RGBA framestore at 600 dpi resolution requires over 100 MB of memory for an A4 page. Also, once the page is rendered to the 8 bit per channel framestore, it must still be converted to the lower bit depth for printing, which is inefficient.
Other RIPs utilize a pixel-sequential rendering method to remove the need for a framestore, and to overcome the over-painting problem. In these systems, each pixel is generated in raster order. All objects to be drawn are retained in a display list. On each scan line, the edges of objects which intersect the scanline are held in increasing order of intersection with the scan line. These points of intersection, or edge crossings, are considered in turn, and activate or deactivate objects in the display list. Between each pair of edges considered, the color data for each pixel which lies between the first edge and the second edge is generated based on which objects are not obscured by opaque objects for that span of pixels (pixel-run). In preparation for the next scanline, the coordinate of intersection of each edge is updated in accordance with the nature of each edge, and the edges are sorted into increasing order of intersection with that scanline. Any new edges are also merged into the list of edges, which is called the active edge list. In the present description, render methods that only render objects in a pixel run that are not obscured by opaque objects are referred to as “pixel sequential render methods”.
Graphics systems which use such pixel sequential rendering have significant advantages in that there is no framestore or line store and no unnecessary over-painting. Objects requiring compositing are processed on a per-pixel basis using each object's original color data.
Pixel sequential rendering suffers when there are large numbers of edges that must be tracked and maintained in sorted order by ascending x, for each scanline. As each edge is updated in a scanline, the edge is re-inserted into the active edge list, usually by an insertion sort. For complex pages, which may consist of hundreds of thousands of edges, the time required to maintain the sorted list of edges for each scanline becomes a large portion of the total time to render a complex page.